package com.sunny;

/**
 * @Author zsunny
 * @Date 2018/9/13 20:15
 * @Mail zsunny@yeah.net
 */
public class Manacher {

    public String pre(String str){
        //预处理增加#
        StringBuilder sb = new StringBuilder(2*str.length()+1);
        sb.append('#');
        for(int i=0;i<str.length();i++){
            sb.append(str.charAt(i)).append('#');
        }
        return sb.toString();
    }

    public int[] solve(String str){
        int len = str.length();
        int[] rec = new int[len];
        rec[0] = 0;
        int c = 0;
        int rig = 0;
        for(int i=1;i<len;i++){
            if(i<rig){
                rec[i] = Integer.min(rec[2*c-i], rig-i);
            }
            while (i+rec[i] < len && i-rec[i] >= 0 && str.charAt(i+rec[i]) == str.charAt(i-rec[i])){
                rec[i]++;
            }
            rec[i]--;
            if(rig < i+rec[i]){
                rig = i+rec[i];
                c = i;
            }
        }
        return rec;
    }

    public static void main(String[] args) {

        Manacher manacher = new Manacher();
        int[] res = manacher.solve(manacher.pre("abcbaadsfabcbcaaasdf"));
        for (int i=0;i<res.length;i++){
            System.out.println(i+" "+res[i]);
        }

    }

}
